| 翻訳と辞書 |
| Constructible function ： ウィキペディア英語版 |
Constructible function
In complexity theory, a time-constructible function is a function ''f'' from natural numbers to natural numbers with the property that ''f''(''n'') can be constructed from ''n'' by a Turing machine in the time of order ''f''(''n''). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.
==Time-constructible definitions==
There are two different definitions of a time-constructible function. In the first definition, a function ''f'' is called time-constructible if there exists a positive integer ''n''0 and Turing machine ''M'' which, given a string 1''n'' consisting of ''n'' ones, stops after exactly ''f''(''n'') steps for all ''n'' ≥ ''n''0. In the second definition, a function ''f'' is called time-constructible if there exists a Turing machine ''M'' which, given a string 1''n'', outputs the binary representation of ''f''(''n'') in ''O''(''f''(''n'')) time (a unary representation may be used instead, since the two can be interconverted in ''O''(''f''(''n'')) time).
There is also a notion of a fully time-constructible function. A function ''f'' is called fully time-constructible if there exists a Turing machine ''M'' which, given a string 1''n'' consisting of ''n'' ones, stops after exactly ''f''(''n'') steps. This definition is slightly less general than the first two but, for most applications, either definition can be used.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Constructible function」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|